To introduce the definition and mathematical properties of a discrete-time one-dimensional RW, we consider a walker starting from the origin. In the RW, in each step the walker flips an unbiased coin and moves to the right (left) if the coin shows a head (tail). After t steps, the position x of the walker is a random variable, and satisfies the binomial distribution

Now, we introduce the definition of stopping time of a RW. We consider a RW in which the walker starts from the origin x = 0. We assume that there is a pair of dam-boards (i.e., boundary) at positions x = ±X_d, and the RW terminates immediately when the walker arrives at one of these dam-boards (Fig. 1). The time T_s at which the process terminates, i.e., the time when the walker arrives at x = X_d or x = −X_d, is defined as the stopping time of RW.

Fig. 1.

	Figure Option ViewDownloadNew Window
	Fig. 1. Bounded discrete-time one-dimensional RW. The walker starts from position 0 and moves to the right or left in each step. The process stops the moment the walker arrives at one of two dam-boards at positions x = ±Xd. In this problem, the stopping time is a random variable.

The stopping time T_s defined above is clearly a random variable; its distribution depends on the position X_d of the dam-boards, and can be denoted as P^(X_d)(T_s). Accordingly, the mean value of the stopping time is also a function of X_d, here denoted as

We now introduce the QW, in which both walker and coin are quantum systems. The total Hilbert space is 𝓗 = 𝓗_w ⊗ 𝓗_c, where 𝓗_w and 𝓗_c are the Hilbert spaces for the walker and coin, respectively. Here, 𝓗_w is spanned by position eigen-states |x〉_w (x = 0,±1,±2,…) of the walker, and 𝓗_c is spanned by “spin” states |H〉_c and |T〉_c, representing the head and tail, respectively, of the coin.

In the beginning of a QW, the walker is at the origin and the coin is prepared in a superposition of head and tail. Specifically, the initial state is

In the first step, the coin is first operated by a Hadamard gate

The physical meaning of U_S is that the walker moves to the right if the coin shows a head, and moves to the left if the coin shows a tail. Thus, after the first step, the state of the total system is

In this QW process, the walker and coin are entangled. Because of quantum interference effects, which can be constructive or destructive, the probability distribution of the walker’s position is completely different from that for RW (Eq. (1)). The properties of this distribution were discussed in Refs. [3], [11], [41] and [43].

It is pointed out that, the QW can be reduced to a classical RW under the decoherence operation in each step.^[44] For our system, we can obtain the results of RW via replacing Eqs. (7) and (8) with and , respectively. Here, ρ(t) is the density operator of the walker and the coin, ρ(0) = |Ψ₀〉〈Ψ₀|, and the decoherence operator 𝓓 is defined as follows: in the bases {|x〉}, all the non-diagonal elements of 𝓓[ρ] are zero, while the diagonal elements of 𝓓[ρ] are the same as the ones of ρ.

Next, we introduce our method for the calculation of the probability distribution of the stopping time of a QW, i.e., the probability distribution for the number of steps T_s at which the walker arrives at the dam-board at x = ±X_d (X_d > 0) for the first time. This probability distribution can be denoted as P^(X_d)(T_s) and can be calculated as follows.

Given the above method, we calculated the probability P^(X_d)(T_s) numerically. Because this QW is bounded between –X_d and X_d, the dimension of the Hilbert space for the walker’s spatial position is 2X_d + 1; similarly, the dimension for the coin’s spin space is 2. Therefore, the density matrix of the system is a matrix (4X_d + 2) × (4X_d + 2) for the entire process. Theoretically, the random variable t extends to infinity and therefore this evolution is capable of working out all probabilities P(t) (Fig. 2). The truncation time is chosen as , which is large enough for the precision of E^(X_d)[T_s]. Through this calculation and a sufficiently large truncation time, the mean value of the stopping time of QW can be obtained.

Fig. 2.

	Figure Option ViewDownloadNew Window
	Fig. 2. P(Xd)(Ts) for QW ((a) and (c)) and RW ((b) and (d)) with Xd = 10 ((a) and (b)) and Xd = 40 ((c) and (d)). Because Xd is even in our cases, we have P(Xd)(Ts) = 0 for odd steps Ts = ±1, ±3, ±5, …. Hence, we have only shown P(Xd)(Ts) for Ts = 0, ±2, ±4, ….

With the method developed above, we numerically calculate the probability distribution of the stopping time T_s for many discrete-time one-dimensional QWs with different positions X_d of the dam-boards. With our result, we further derive the mean E^(X_d)[T_s] of T_s. We find that for fixed values of X_d, the mean value of the stopping time of a QW and a RW are same. Specifically, for a QW we also have . We illustrate this result in Fig. 3.

Fig. 3.

	Figure Option ViewDownloadNew Window
	Fig. 3. Mean value E(Xd)[Ts] of the stopping time of a discrete-time one-dimensional QW. The red solid line is the result ; the black line is the numerical result for a QW, which is given by the method in Section 3.2.

Although the mean value of the stopping time T_s for both QW and RW are the same, the probability distribution of T_s for these two cases are completely different. Figure 2 illustrates the probability distribution P^(X_d)(T_s) corresponding to X_d = 10 and X_d = 40, for both QW and RW. We find that for a given value of X_d, P^(X_d)(T_s) for a QW peaks at a smaller T_s, and has a larger peak value. That is, if we define T_max as the value of T_s at which the probability density P^(X_d)(T_s) takes its maximum value, and define P_max as the corresponding peak value (i.e., P_max ≡ P^(X_d)(T_max)), then QW has a smaller T_max and a larger P_max. For instance, as shown in Fig. 2, when X_d = 40, for QW we have T_max = 60 and P_max = 0.1087, whereas for RW we have T_max = 532 and P_max = 1.157 × 10⁻³.

Our numerical calculations show that this character is universal for QW for different values of X_d. From Fig. 4, when X_d is large (larger than 10), we have and for QW and and for RW. Therefore, we know that as X_d increases, the disparity in stopping times for QW and RW increases.

Fig. 4.

	Figure Option ViewDownloadNew Window
	Fig. 4. (a) Time Tmax for the maximum point in the probability distribution P(Xd)(Ts); (b) the peak value Pmax of P(Xd)(Ts) at time Tmax.

In addition to the above features, our calculation also shows that when T_s is large, the decay of P^(X_d)(T_s) for QW is slower than that for RW (Fig. 5). This explains the fact that although the probability distribution P^(X_d)(T_s) peaks at a shorter time for QW, the mean of the stopping time T_s is the same for both QW and RW.

Fig. 5.

	Figure Option ViewDownloadNew Window
	Fig. 5. Probability distribution P(Xd)(Ts) for QW and RW of Xd = 10 in the large-Ts region.

In the section above, we showed that in comparison with a RW, the probability distribution P^(X_d)(T_s) of the stopping time for a QW peaks at smaller values of T_s, and has a larger peak value P_max. This property implies that for a given value of X_d, the walker of a QW has a large probability (more than 50%) of arriving at the dam-boards earlier than a walker of a RW. That is, we have a large probability for the fact that “QW is faster”.

To verify this result, we numerically calculated the probability Q(X_d) for the fact that “QW is faster”. This probability can be reasonably defined as

Fig. 6.

	Figure Option ViewDownloadNew Window
	Fig. 6. Probability Q(Xd) that a walker arrives faster by a QW than by a RW.

Finally, we study the cumulative probability for a QW, which is defined as the probability that the walker arrives at the dam-boards before time T. Denoted as F^(X_d)(T), we can express it as

In Fig. 7, we show the cumulative probability F^(X_d)(T) for both QW and RW with X_d = 40. For a QW, the cumulative probability increases very fast for small T. As a result, for short times T, a walker of a QW has a larger probability of arriving at the dam-boards than a walker of the RW. The reason is that the probability distribution P^(X_d)(T_s) peaks at a shorter time and has a larger peak value for a QW, as demonstrated in Section 4.1.

Fig. 7.

	Figure Option ViewDownloadNew Window
	Fig. 7. Cumulative probability F(Xd)(T) for QW and RW with Xd = 40.

Figure 7 also shows that when time T is increased, the cumulative probability F^(X_d)(T) of a RW can exceed that for a QW. As a result, when T is sufficiently large, the cumulative probability for a RW is larger than that for a QW. This is consistent with the fact that the mean of the stopping time is the same for both QW and RW.